/**
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 *
 *思路：在归并过程中计算逆序对
 * 比如：2,3,5,9和1,4,6,8这两个其实是一个数组在归并过程中两个区间里的数字已经有序，然后我们比较2和1发现2比1大，
 * 又因为2,3,5,9由于前面的归并已经有序，所以说2，3,5,9都比1大都是逆序对，然后这个区间又是left到mid所以逆序对的个数：mid-left+1
 * 然后走到4，发现3比4小，left++，正常归并，然后5比4大，用mid-left+1计算逆序数（其实就是算5后面多少个数字），以此类推
 * 题解：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/
 */
class ReversePairsGuiBin {
    public int reversePairs(int[] nums) {
        return reversePairs(nums,0,nums.length-1);
    }
    public int reversePairs(int[] nums,int left,int right){
        if(left>=right){
            return 0;
        }
        int mid=left+((right-left)>>>1);
        int leftCount=reversePairs(nums,left,mid);//左半区间归并时计算得到的逆序数
        int rightCount=reversePairs(nums,mid+1,right);//右半区间归并时计算得到的逆序数
        if(nums[mid]<=nums[mid+1]){//如果已经有序无需和并
            return leftCount+rightCount;
        }
        int cossCount=merge(nums,left,mid,right);//左半区间和右半区间归并计算逆序数
        return leftCount+rightCount+cossCount;
    }
    public int merge(int[] nums,int left,int mid,int right){
        int count=0;
        int s1=left;
        int b1=mid;
        int s2=mid+1;
        int b2=right;
        int[] tmp=new int[right-left+1];
        int k=0;
        while(s1<=b1&&s2<=b2){
            if(nums[s1]<=nums[s2]){
                tmp[k++]=nums[s1++];
            }else{
                count+=(b1-s1+1);
                tmp[k++]=nums[s2++];
            }
        }
        while(s1<=b1){
            tmp[k++]=nums[s1++];
        }
        while(s2<=b2){
            tmp[k++]=nums[s2++];
        }
        for(int i=0;i<k;i++){
            nums[i+left]=tmp[i];
        }
        return count;
    }
}